{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximize Distance to Closest Person"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxDistToClosest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #到最近的人的最大距离"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个数组 <code>seats</code> 表示一排座位，其中 <code>seats[i] = 1</code> 代表有人坐在第 <code>i</code> 个座位上，<code>seats[i] = 0</code> 代表座位 <code>i</code> 上是空的（<strong>下标从 0 开始</strong>）。</p>\n",
    "\n",
    "<p>至少有一个空座位，且至少有一人已经坐在座位上。</p>\n",
    "\n",
    "<p>亚历克斯希望坐在一个能够使他与离他最近的人之间的距离达到最大化的座位上。</p>\n",
    "\n",
    "<p>返回他到离他最近的人的最大距离。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/10/distance.jpg\" style=\"width: 650px; height: 257px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>seats = [1,0,0,0,1,0,1]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：\n",
    "</strong>如果亚历克斯坐在第二个空位（seats[2]）上，他到离他最近的人的距离为 2 。\n",
    "如果亚历克斯坐在其它任何一个空位上，他到离他最近的人的距离为 1 。\n",
    "因此，他到离他最近的人的最大距离是 2 。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>seats = [1,0,0,0]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "如果亚历克斯坐在最后一个座位上，他离最近的人有 3 个座位远。\n",
    "这是可能的最大距离，所以答案是 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>seats = [0,1]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 <= seats.length <= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>seats[i]</code> 为 <code>0</code> 或 <code>1</code></li>\n",
    "\t<li>至少有一个 <strong>空座位</strong></li>\n",
    "\t<li>至少有一个 <strong>座位上有人</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximize-distance-to-closest-person](https://leetcode.cn/problems/maximize-distance-to-closest-person/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximize-distance-to-closest-person](https://leetcode.cn/problems/maximize-distance-to-closest-person/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,0,0,0,1,0,1]', '[1,0,0,0]', '[0,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        n = len(seats)\n",
    "        if n==2: return 1\n",
    "        dp = [0]*n\n",
    "        dp[0] = inf if not seats[0] else 0\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            if not seats[i]:\n",
    "                if not seats[i-1]: dp[i] = dp[i-1]+1\n",
    "                else: dp[i] = 1\n",
    "        \n",
    "        for j in range(n-2, -1, -1):\n",
    "            if not seats[j]:\n",
    "                if not seats[j+1]: dp[j] = min(dp[j], dp[j+1]+1)\n",
    "                else: dp[j] = min(dp[j], 1)\n",
    "        \n",
    "        return max(dp)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        a=''.join(str(i) for i in seats)\n",
    "        a=a.split('1')\n",
    "        n=max(len(x) for x in a)\n",
    "        b=max((n+1)//2,len(a[0]),len(a[-1]))\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        sum = 0\n",
    "        final = 0\n",
    "        for i in range(len(seats)):\n",
    "            if seats[i] == 0:\n",
    "                sum += 1 \n",
    "            else:\n",
    "                final = max(final, sum)\n",
    "                sum = 0\n",
    "        if final < sum:\n",
    "            final = sum\n",
    "        final_0 = int((final + 1 )/ 2)\n",
    "        for i in range(len(seats)):\n",
    "            if seats[i] == 1:\n",
    "                final_1 = i\n",
    "                break\n",
    "        seats = seats[::-1]\n",
    "        for i in range(len(seats)):\n",
    "            if seats[i] == 1:\n",
    "                final_2 = i\n",
    "                break\n",
    "        return max(final_0, final_1, final_2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        dis=i=0\n",
    "        Seats=[1]+seats\n",
    "        for index in range(len(Seats)):\n",
    "            if Seats[index]:\n",
    "                dis=max(dis,abs(index-i))\n",
    "                i=max(i,index)\n",
    "        dis//=2\n",
    "        if not seats[0]:\n",
    "            dis=max(seats.index(1),dis)\n",
    "        if not seats[-1]:\n",
    "            dis=max(len(Seats)-i-1,dis)\n",
    "        return dis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\r\n",
    "        n=len(seats)\r\n",
    "        right=[0]*n\r\n",
    "        res=0\r\n",
    "        tmp=inf\r\n",
    "        for i in range(n-1,-1,-1):\r\n",
    "            if seats[i]==1:\r\n",
    "                right[i]=0\r\n",
    "                tmp=0\r\n",
    "            else:\r\n",
    "                tmp+=1\r\n",
    "                right[i]=tmp\r\n",
    "        tmp=inf\r\n",
    "        for i in range(n):\r\n",
    "            if seats[i]==1:\r\n",
    "                tmp=0\r\n",
    "            else:\r\n",
    "                tmp+=1\r\n",
    "                res=max(res,min(tmp,right[i]))\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        first = last = None\n",
    "        d = 0\n",
    "        for i, c in enumerate(seats):\n",
    "            if c:\n",
    "                if last is not None:\n",
    "                    d = max(d, i - last)\n",
    "                if first is None:\n",
    "                    first = i\n",
    "                last = i\n",
    "        return max(first, len(seats) - last - 1, d // 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        import math\n",
    "        # if seats.count(1) == 1:\n",
    "        #     idx = seats.index(1)\n",
    "        #     return max(idx, len(seats) - (idx + 1))\n",
    "        dis = 0\n",
    "        left = seats.index(1)\n",
    "        right = left + 1\n",
    "        while right < len(seats):\n",
    "            if seats[left] == 1 and seats[right] == 1:\n",
    "                dis = max(dis, right - left - 1)\n",
    "                left = right\n",
    "            right += 1\n",
    "        left_idx = seats.index(1)\n",
    "        right_idx = seats[::-1].index(1)\n",
    "        tmp = max(left_idx, right_idx)\n",
    "        return max(math.ceil(dis / 2), tmp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        import math\n",
    "        # if seats.count(1) == 1:\n",
    "        #     idx = seats.index(1)\n",
    "        #     return max(idx, len(seats) - (idx + 1))\n",
    "        dis = 0\n",
    "        left = seats.index(1)\n",
    "        right = left + 1\n",
    "        while right < len(seats):\n",
    "            if seats[left] == 1 and seats[right] == 1:\n",
    "                dis = max(dis, right - left - 1)\n",
    "                left = right\n",
    "            right += 1\n",
    "        left_idx = seats.index(1)\n",
    "        right_idx = seats[::-1].index(1)\n",
    "        tmp = max(left_idx, right_idx)\n",
    "        return max(math.ceil(dis / 2), tmp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        ans = 0\n",
    "        while seats[ans] != 1:\n",
    "            ans += 1\n",
    "\n",
    "        dis = 0\n",
    "        for i in seats[ans + 1:]:\n",
    "            if i:\n",
    "                ans = max(ans, (dis + 1) >> 1)\n",
    "                dis = 0\n",
    "            else:\n",
    "                dis += 1\n",
    "\n",
    "        return max(ans, dis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        ans = 0\n",
    "        while not seats[ans]:\n",
    "            ans += 1\n",
    "\n",
    "        dis = 0\n",
    "        for i in seats[ans + 1:]:\n",
    "            if i:\n",
    "                ans = max(ans, dis + 1 >> 1)\n",
    "                dis = 0\n",
    "            else:\n",
    "                dis += 1\n",
    "\n",
    "        return max(ans, dis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        distance = -1\n",
    "        pre = -1\n",
    "        i = 0\n",
    "        n = len(seats)\n",
    "        while i < n:\n",
    "            if seats[i] == 0:\n",
    "                i += 1\n",
    "                continue\n",
    "            if i == pre + 1:\n",
    "                pre = i\n",
    "                i += 1\n",
    "                continue\n",
    "\n",
    "            if pre == -1:\n",
    "                distance = i\n",
    "            else:\n",
    "                if (i - pre) // 2 > distance:\n",
    "                    distance = (i - pre) // 2\n",
    "            pre = i\n",
    "            i += 1\n",
    "\n",
    "        return max(distance, n - 1 - pre)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        ans = 0\n",
    "        while seats[ans] == 0:\n",
    "            ans += 1\n",
    "\n",
    "        dis = 0\n",
    "        for i in seats[ans + 1:]:\n",
    "            if i:\n",
    "                ans = max(ans, dis + 1 >> 1)\n",
    "                dis = 0\n",
    "            else:\n",
    "                dis += 1\n",
    "\n",
    "        return max(ans, dis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        #定义第一个人和最后一个人你的位置\n",
    "        first = last = None\n",
    "        #定义最长长度\n",
    "        d = 0\n",
    "        #枚举遍历seats数组\n",
    "        for i, c in enumerate(seats):\n",
    "            #如果当前的值为1时，就是找到第一个人的位置的时候\n",
    "            if c==1:\n",
    "                #如果最后一个人的位置不为空，意思就是找到了下个人值为1的\n",
    "                if last is not None:\n",
    "                    #更新最长长度\n",
    "                    d = max(d, i - last)\n",
    "                #如果当前first为空，则意味着还没找到第一个人，那么当前的位置就是第一个人的位置，也就意味着该种情况是前面出现的都是0\n",
    "                if first is None:\n",
    "                    first = i\n",
    "                #更新当前找到已坐座位的人的位置\n",
    "                last = i\n",
    "        return max(first, len(seats) - last - 1, d//2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        a = []\n",
    "        b = 0\n",
    "        c = seats[-1] == 0\n",
    "        if c:\n",
    "            seats.insert(-1, 1)\n",
    "\n",
    "        for i in range(len(seats)):\n",
    "            if seats[i]:\n",
    "                a.append(i - b)\n",
    "                b = i\n",
    "        b = [a[0], max(a)//2]\n",
    "        if c:\n",
    "            b.append(a[-1])\n",
    "        else:\n",
    "            b.append(a[-1]//2)\n",
    "        # return max(a) if (a[-1] == max(a) and not c) or (a[0] == max(a)) else max(a) // 2\n",
    "        return max(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        n = len(seats)\n",
    "        l = 0  # 左指针\n",
    "        while l < n and seats[l] == 0: \n",
    "            l += 1   # 找到首个有人座位\n",
    "        res = l    # 第一个区间的插空位置为首位0，间距为l - 0 = l\n",
    "        while l < n:\n",
    "            r = l + 1\n",
    "            while r < n and seats[r] == 0: \n",
    "                r += 1   # 找到下一个有人座位\n",
    "            if r == n:\n",
    "                res = max(res, n - 1 - l) # r到达边界，l指向最后一个1；最后一个区间的插空位置为末尾n-1，间距为n - 1- l\n",
    "            else:\n",
    "                res = max(res, (r - l) // 2)   # 否则，插空位置为区间[l, r]中点\n",
    "            l = r  # 更新l，查找下一个有人座位区间\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        first = last = None\n",
    "        d = 0\n",
    "        max = lambda x, y: x if x > y else y\n",
    "        for i, x in enumerate(seats):\n",
    "            if x:\n",
    "                if last is not None:\n",
    "                    d = max(d, i - last)\n",
    "                if first is None:\n",
    "                    first = i\n",
    "                last = i\n",
    "        return max(max(first, len(seats) - last - 1), d // 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        #定义左右指针\n",
    "        #分别记录1的左右位置\n",
    "        left, right, ans = 0, 0, 0\n",
    "        #1.求出1的最左边位置\n",
    "        while left < len(seats) and seats[left] == 0:\n",
    "            left += 1\n",
    "        ans = left #更新最大值\n",
    "        #2.查找1的最右边位置\n",
    "        right = left + 1\n",
    "        while right < len(seats):\n",
    "            while right < len(seats) and seats[right] == 0:\n",
    "                right += 1\n",
    "            #判断是否末尾\n",
    "            if right == len(seats):\n",
    "                ans = max(len(seats) - left - 1, ans)\n",
    "            else:\n",
    "            #中间更新\n",
    "                ans = max((right - left) // 2, ans)\n",
    "                left = right\n",
    "            right += 1\n",
    "        return ans\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "                \n",
    "    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        first = last = None\n",
    "        d = 0\n",
    "        for i, c in enumerate(seats):\n",
    "            if c:\n",
    "                if last is not None:\n",
    "                    d = max(d, i - last)\n",
    "                if first is None:\n",
    "                    first = i\n",
    "                last = i\n",
    "        return max(first, len(seats) - last - 1, d // 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        #定义第一个人和最后一个人你的位置\n",
    "        first = last = -1\n",
    "        #定义最长长度\n",
    "        d = 0\n",
    "        #枚举遍历seats数组\n",
    "        for i, c in enumerate(seats):\n",
    "            #如果当前的值为1时，就是找到第一个人的位置的时候\n",
    "            if c==1:\n",
    "                #如果最后一个人的位置不为空，意思就是找到了下个人值为1的\n",
    "                if last !=-1:\n",
    "                    #更新最长长度\n",
    "                    d = max(d, i - last)\n",
    "                #如果当前first为空，则意味着还没找到第一个人，那么当前的位置就是第一个人的位置，也就意味着该种情况是前面出现的都是0\n",
    "                if first ==-1:\n",
    "                    first = i\n",
    "                #更新当前找到已坐座位的人的位置\n",
    "                last = i\n",
    "        #返回三种情况下的值，即左边为1，右边为1和中间出现1的情况，中间出现1的时候就是两个1之间的中间就是距离最大的情况\n",
    "        return max(first, len(seats) - last - 1, d//2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        ans, empty_seat = 0, 0\n",
    "        for i, seat in enumerate(seats):\n",
    "            if seat == 0: empty_seat += 1\n",
    "            else:\n",
    "                ans = max(ans, (empty_seat+1)//2)\n",
    "                empty_seat = 0\n",
    "        return max(ans, seats.index(1), seats[::-1].index(1))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        n = len(seats)\n",
    "        l = 0  # 左指针\n",
    "        while l < n and seats[l] == 0: \n",
    "            l += 1   # 找到首个有人座位\n",
    "        res = l    # 第一个区间的插空位置为首位0，间距为l - 0 = l\n",
    "        while l < n:\n",
    "            r = l + 1\n",
    "            while r < n and seats[r] == 0: \n",
    "                r += 1   # 找到下一个有人座位\n",
    "            if r == n:\n",
    "                res = max(res, n - 1 - l) # r到达边界，l指向最后一个1；最后一个区间的插空位置为末尾n-1，间距为n - 1- l\n",
    "            else:\n",
    "                res = max(res, (r - l) // 2)   # 否则，插空位置为区间[l, r]中点\n",
    "            l = r  # 更新l，查找下一个有人座位区间\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        #定义第一个人和最后一个人你的位置\n",
    "        first = last = None\n",
    "        #定义最长长度\n",
    "        d = 0\n",
    "        #枚举遍历seats数组\n",
    "        for i, c in enumerate(seats):\n",
    "            #如果当前的值为1时，就是找到第一个人的位置的时候\n",
    "            if c==1:\n",
    "                #如果最后一个人的位置不为空，意思就是找到了下个人值为1的\n",
    "                if last is not None:\n",
    "                    #更新最长长度\n",
    "                    d = max(d, i - last)\n",
    "                #如果当前first为空，则意味着还没找到第一个人，那么当前的位置就是第一个人的位置，也就意味着该种情况是前面出现的都是0\n",
    "                if first is None:\n",
    "                    first = i\n",
    "                #更新当前找到已坐座位的人的位置\n",
    "                last = i\n",
    "        #返回三种情况下的值，即左边为1，右边为1和中间出现1的情况。\n",
    "        return max(first, len(seats) - last - 1, d//2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        n = len(seats)\n",
    "        max_distance = 0\n",
    "        last_person = -1\n",
    "        \n",
    "        for i in range(n):\n",
    "            if seats[i] == 1:\n",
    "                if last_person == -1:\n",
    "                    # 如果第一个人在索引0处\n",
    "                    max_distance = i\n",
    "                else:\n",
    "                    # 计算连续人员之间的距离\n",
    "                    max_distance = max(max_distance, (i - last_person) // 2)\n",
    "                last_person = i\n",
    "        \n",
    "        # 如果最后一个座位是空的，计算到它的距离\n",
    "        if seats[-1] == 0:\n",
    "            max_distance = max(max_distance, n - 1 - last_person)\n",
    "        return max_distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        #定义第一个人和最后一个人你的位置\n",
    "        first = last = None\n",
    "        #定义最长长度\n",
    "        d = 0\n",
    "        #枚举遍历seats数组\n",
    "        for i, c in enumerate(seats):\n",
    "            #如果当前的值为1时，就是找到第一个人的位置的时候\n",
    "            if c==1:\n",
    "                #如果最后一个人的位置不为空，意思就是找到了下个人值为1的\n",
    "                if last is not None:\n",
    "                    #更新最长长度\n",
    "                    d = max(d, i - last)\n",
    "                #如果当前first为空，则意味着还没找到第一个人，那么当前的位置就是第一个人的位置，也就意味着该种情况是前面出现的都是0\n",
    "                if first is None:\n",
    "                    first = i\n",
    "                #更新当前找到已坐座位的人的位置\n",
    "                last = i\n",
    "        #返回三种情况下的值，即左边为1，右边为1和中间出现1的情况。\n",
    "        return max(first, len(seats) - last - 1, d//2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        n = len(seats)\n",
    "        L, maxVal = -2*n, 0\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if seats[i]:\n",
    "                maxVal = max(maxVal, min(i, (i - L) // 2))\n",
    "                L = i\n",
    "            i += 1\n",
    "        return max(maxVal, n - L - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        #定义左右指针\n",
    "        #分别记录1的左右位置\n",
    "        left, right, ans = 0, 0, 0\n",
    "        #1.求出1的最左边位置\n",
    "        while left < len(seats) and seats[left] == 0:\n",
    "            left += 1\n",
    "        ans = max(ans, left) #更新最大值\n",
    "        #2.查找1的最右边位置\n",
    "        right = left + 1\n",
    "        while right < len(seats):\n",
    "            while right < len(seats) and seats[right] == 0:\n",
    "                right += 1\n",
    "            #判断是否末尾\n",
    "            if right == len(seats):\n",
    "                ans = max(len(seats) - left - 1, ans)\n",
    "            else:\n",
    "                ans = max((right - left) // 2, ans)\n",
    "                left = right\n",
    "            right += 1\n",
    "        return ans\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "                \n",
    "    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        dis = 0\n",
    "        k = 0\n",
    "        while not seats[k]:\n",
    "            dis = dis+1\n",
    "            k = k+1\n",
    "        num_seats = len(seats)\n",
    "        interval = 0\n",
    "        k = k+1\n",
    "        while k<num_seats:\n",
    "            if not seats[k]:\n",
    "                interval = interval+1\n",
    "            else:\n",
    "                if (interval>0) and ((interval+1)//2>dis):\n",
    "                    dis = (interval+1)//2\n",
    "                interval = 0\n",
    "            k = k+1\n",
    "            if k == num_seats:\n",
    "                if interval+1>dis:\n",
    "                    return interval\n",
    "        return dis\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        key = 0 \n",
    "        l = len(seats)\n",
    "        i = 0\n",
    "        while seats[i] == 0:\n",
    "            i += 1\n",
    "        maxans = i\n",
    "        while i < l:\n",
    "            if seats[i] == 1:\n",
    "                maxans = max(maxans,(i - key) // 2)\n",
    "                key = i\n",
    "            i += 1\n",
    "        maxans = max(maxans,  l - key - 1);\n",
    "        return maxans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        first = last = None\n",
    "        d = 0\n",
    "        for i, c in enumerate(seats):\n",
    "            if c:\n",
    "                if last is not None:\n",
    "                    d = max(d, i - last)\n",
    "                if first is None:\n",
    "                    first = i\n",
    "                last = i\n",
    "        return max(first, len(seats) - last - 1, d // 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "    #     if len(seats) == 2: return 1\n",
    "    #     res = 0\n",
    "    #     for i in range(len(seats)):\n",
    "    #         res = max(res, self.min_distance(seats, i))\n",
    "    #     return res\n",
    "\n",
    "    # def min_distance(self, seats, mid):\n",
    "    #     left, right = mid, mid\n",
    "    #     while left>=0 and right<len(seats):\n",
    "    #         if seats[left] == 0:\n",
    "    #             left -= 1\n",
    "    #         elif seats[right] == 0:\n",
    "    #             right += 1\n",
    "    #         else:\n",
    "    #             break\n",
    "    #     if (seats[0] == 0 or seats[-1] == 0) and (right == len(seats) or left == -1):\n",
    "    #         return max(right - mid, mid - left)\n",
    "    #     else:\n",
    "    #         return min(right - mid, mid - left)\n",
    "\n",
    "\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        max_interval = 0\n",
    "        left = -1\n",
    "        for right in range(len(seats)):\n",
    "            if seats[right] != 0:\n",
    "                if left == -1:\n",
    "                    max_interval = max(max_interval, right)\n",
    "                else:\n",
    "                    max_interval = max(max_interval, (right - left)//2)\n",
    "                left = right\n",
    "        max_interval = max(max_interval, len(seats) - left - 1)\n",
    "        return max_interval            \n",
    "\n",
    "\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        left, right = 0, 0\n",
    "        max_distance = 0\n",
    "        while right < len(seats):\n",
    "            if seats[right] == 1:\n",
    "                if seats[left] == 1:\n",
    "                    max_distance = max(max_distance, (right - left)//2)\n",
    "                else:\n",
    "                    max_distance = max(max_distance, right - left)\n",
    "                left = right\n",
    "            right += 1\n",
    "        max_distance = max(max_distance, len(seats) - 1 - left)\n",
    "        return max_distance\n",
    "            \n",
    "            \n",
    "\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        max_distance = 1\n",
    "        left, right = 0, 0\n",
    "        while right < len(seats):\n",
    "            if seats[right] == 1:\n",
    "                if seats[left] == 1:\n",
    "                    max_distance = max(max_distance, (right - left)//2)\n",
    "                else:\n",
    "                    max_distance = max(max_distance, right)\n",
    "                left = right\n",
    "            right += 1\n",
    "        max_distance = max(max_distance, len(seats) - 1 - left)\n",
    "        return max_distance\n",
    "\n",
    "    def maxDistToClosest(self, seats):\n",
    "        left, right = 0, 0\n",
    "        max_len = 0\n",
    "        while right < len(seats):\n",
    "            if seats[right] == 1:\n",
    "                if seats[left] == 1:\n",
    "                    max_len = max(max_len, (right - left)//2)\n",
    "                else:\n",
    "                    max_len = max(max_len, right - left)\n",
    "                left = right\n",
    "            right += 1\n",
    "        max_len = max(max_len, len(seats) - left - 1)\n",
    "        return max_len\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        #定义左右指针\n",
    "        #分别记录1的左右位置\n",
    "        left, right, ans = 0, 0, 0\n",
    "        #1.求出1的最左边位置\n",
    "        while left < len(seats) and seats[left] == 0:\n",
    "            left += 1\n",
    "        ans = left #更新最大值\n",
    "        #2.查找1的最右边位置\n",
    "        right = left + 1\n",
    "        while right < len(seats):\n",
    "            while right < len(seats) and seats[right] == 0:\n",
    "                right += 1\n",
    "            #判断是否末尾\n",
    "            if right == len(seats):\n",
    "                ans = max(len(seats) - left - 1, ans)\n",
    "            else:\n",
    "            #中间更新\n",
    "                ans = max((right - left) // 2, ans)\n",
    "                left = right\n",
    "            right += 1\n",
    "        return ans\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "                \n",
    "    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        #定义第一个人和最后一个人你的位置\n",
    "        first = last = None\n",
    "        #定义最长长度\n",
    "        d = 0\n",
    "        #枚举遍历seats数组\n",
    "        for i, c in enumerate(seats):\n",
    "            #如果当前的值为1时，就是找到第一个人的位置的时候\n",
    "            if c==1:\n",
    "                #如果最后一个人的位置不为空，意思就是找到了下个人值为1的\n",
    "                if last is not None:\n",
    "                    #更新最长长度\n",
    "                    d = max(d, i - last)\n",
    "                #如果当前first为空，则意味着还没找到第一个人，那么当前的位置就是第一个人的位置，也就意味着该种情况是前面出现的都是0\n",
    "                if first is None:\n",
    "                    first = i\n",
    "                #更新当前找到已坐座位的人的位置\n",
    "                last = i\n",
    "        #返回三种情况下的值，即左边为1，右边为1和中间出现1的情况，中间出现1的时候就是两个1之间的中间就是距离最大的情况\n",
    "        return max(first, len(seats) - last - 1, d//2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        #一定会有一个人\n",
    "        #1.左边有人右边有人 结果左右下标距离一半\n",
    "        #2.左边没人右边有人  结果为末端与初始的距离\n",
    "        #3.左边有人右边没人  结果为末端与左端的距离\n",
    "        # c0, ans = 0, 0\n",
    "        \n",
    "        i = 0\n",
    "        ans = 0\n",
    "        l = -1\n",
    "        while i < len(seats):\n",
    "            c0 = 0\n",
    "            while i < len(seats) and seats[i] == 0:\n",
    "                c0 += 1\n",
    "                i += 1\n",
    "            #更新结果\n",
    "            if i < len(seats) and seats[i] == 1:\n",
    "                #判断左边是否有人\n",
    "                if l == -1:\n",
    "                    #左边没人右边有人\n",
    "                    ans = max(ans, c0)\n",
    "                else:\n",
    "                    #左边有人右边有人\n",
    "                    ans = max(ans, (c0 + 1) // 2)\n",
    "                l = i\n",
    "            else:\n",
    "                #右边没人\n",
    "                ans = max(ans, c0)\n",
    "            i += 1\n",
    "        return ans\n",
    "    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        _len = len(seats)\n",
    "        _max = 0\n",
    "        _bf = -1\n",
    "        idx = 0\n",
    "        while idx  < _len and (_len - _bf - 1) // (1 + seats[-1]) > _max:\n",
    "            if seats[idx] == 1:\n",
    "                if _bf == -1:\n",
    "                    _max = max(idx - 1, _max)\n",
    "                else:\n",
    "                    _max = max((idx - _bf - 1) // 2, _max)\n",
    "                _bf = idx + 1\n",
    "\n",
    "            idx += 1\n",
    "\n",
    "        if seats[-1] == 0 and idx == _len:\n",
    "            _max = max(_max, _len - _bf - 1)\n",
    "\n",
    "        return _max + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        left,mid, right, n= 0, 0, 0, len(seats)\n",
    "        while seats[0]== 0:\n",
    "            left+= 1\n",
    "            seats.pop(0)\n",
    "        while seats[-1]== 0:\n",
    "            right+= 1\n",
    "            seats.pop(-1)\n",
    "        max_ans= max(left, right)\n",
    "        for i in seats:\n",
    "            if i== 0:\n",
    "                mid+= 1\n",
    "                continue\n",
    "            max_ans= max(max_ans, round(mid/2+0.1))\n",
    "            mid= 0\n",
    "        return max_ans\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        fast = 0\n",
    "        slow = 0\n",
    "        max_fast = 0\n",
    "        max_slow = 0\n",
    "        res=1\n",
    "        for i in range(len(seats)):\n",
    "            if i==len(seats)-1:\n",
    "                if seats[i]==1:\n",
    "                    if fast==slow:\n",
    "                        if seats[slow]==1:\n",
    "                            fast=i\n",
    "                            res = max(res,int((fast+slow)/2)-slow)\n",
    "                        else:\n",
    "                            fast = i\n",
    "                            res = max(res,fast-slow)\n",
    "                    else:\n",
    "                        slow = fast\n",
    "                        fast = i\n",
    "                        res = max(res,int((fast+slow)/2)-slow)\n",
    "                else:\n",
    "                    if fast==slow:\n",
    "                        res = max(i-slow,res)\n",
    "                    else:\n",
    "                        res = max(i-fast,res)\n",
    "                break\n",
    "            if seats[i]==1:\n",
    "                if fast==slow:\n",
    "                    if seats[slow]==0:\n",
    "                        fast=i\n",
    "                        res = max(res,i-slow)\n",
    "                    else:\n",
    "                        fast=i\n",
    "                        res = max(res,int((fast+slow)/2)-slow)\n",
    "                else:\n",
    "                    slow = fast\n",
    "                    fast = i\n",
    "                    res = max(res,int((fast+slow)/2)-slow)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        left_index = -30000\n",
    "        left = []\n",
    "        right = []\n",
    "\n",
    "        for key, item in enumerate(seats):\n",
    "            if item == 0:\n",
    "                left.append(key - left_index)\n",
    "            else:\n",
    "                left_index = key\n",
    "                left.append(key - left_index)\n",
    "        right_index = 30000\n",
    "        for key in range(len(seats) - 1, -1, -1):\n",
    "            if seats[key] == 0:\n",
    "                right.insert(0,right_index-key)\n",
    "            else:\n",
    "                right_index = key\n",
    "                right.insert(0,right_index-key)\n",
    "        max_dis = min(left[0], right[0])\n",
    "        for i in range(0, len(seats)):\n",
    "            now_dis = min(left[i], right[i])\n",
    "            if now_dis <= max_dis:\n",
    "                continue\n",
    "            else:\n",
    "                max_dis = now_dis\n",
    "        return max_dis\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        a = [0] * (len(seats) + 1)\n",
    "        b = [0] * (len(seats) + 1)\n",
    "        n = len(seats)\n",
    "        # 获取左边的位置\n",
    "        pre = 1e9\n",
    "        for i in range(n):\n",
    "            if seats[i] == 1:\n",
    "                pre = i\n",
    "            else:\n",
    "                a[i] = pre\n",
    "        # 获取右边的位置\n",
    "        nex = 1e9\n",
    "        for i in range(n - 1,-1,-1):\n",
    "            if seats[i] == 1:\n",
    "                nex = i\n",
    "            else:\n",
    "                b[i] = nex\n",
    "        maxn = -1e9\n",
    "        for i in range(n):\n",
    "            if seats[i] != 1:\n",
    "                maxn = max(maxn,min(abs(i - a[i]),abs(i - b[i])))\n",
    "        return maxn\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        # Alex只能坐在seat[i]=0的位置上\n",
    "        # 对于每个seat[i]=0：计算i到左边最近1的距离   +    计算i到右边最近1的距离  --> 二者中最小的那个作为社恐距离\n",
    "        # 开头和结束需要注意一下\n",
    "        # 1 计算i到左边最近1的距离\n",
    "        temp = -100000\n",
    "        dis_left = []       # 计算i到左边最近1的距离  \n",
    "        dis_right = []      # 计算i到右边最近1的距离\n",
    "        for i in range(len(seats)):\n",
    "            if seats[i] == 1:\n",
    "                temp = i\n",
    "            else:   # 为0\n",
    "                dis_left.append(i - temp)\n",
    "        # 2 计算i到右边最近1的距离\n",
    "        temp = - 100000\n",
    "        for i in range(len(seats)):\n",
    "            if seats[-i-1] == 1:\n",
    "                temp = i\n",
    "            else:\n",
    "                dis_right.append(i - temp)\n",
    "        # 计算max(min(dis_left,dis_right))\n",
    "        # print(dis_left,dis_right)\n",
    "        results = 0\n",
    "        for i in range(len(dis_left)):\n",
    "            results = max(results, min(dis_left[i],dis_right[-i-1]))\n",
    "        return results\n",
    "\n",
    "        # # 用指针法做：p指向1的位置，q指向1的位置，p在q的左边，遍历i\n",
    "        # for i in range(len(seats)):\n",
    "        #     if seats[i] == 1:\n",
    "        #         p = seats[i]\n",
    "        #     else:\n",
    "        #         dis = i - p\n",
    "                \n",
    "        # print(seats)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        n = len(seats)\n",
    "        left, leftGap = [], float(\"inf\") # 如果左侧第一个为0表明，当前位置可以被作为答案\n",
    "        for x in seats:\n",
    "            if x == 1:\n",
    "                leftGap = 0\n",
    "            else:\n",
    "                leftGap += 1\n",
    "            left.append(leftGap)\n",
    "        right, rightGap = deque(), float(\"inf\")\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if seats[i] == 1:\n",
    "                rightGap = 0\n",
    "            else:\n",
    "                rightGap += 1\n",
    "            right.appendleft(rightGap)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if left[i] + right[i] == 0:\n",
    "                continue\n",
    "            ans = max(ans, min(left[i], right[i]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        ans = 0\n",
    "        idx = []\n",
    "        for i, x in enumerate(seats):\n",
    "            if x == 1:\n",
    "                idx.append(i)\n",
    "        if idx[0] != 0:\n",
    "            ans = max(ans, idx[0])\n",
    "        if idx[-1] != len(seats) -1:\n",
    "            ans = max(ans, len(seats) -1-idx[-1])\n",
    "        for i in range(1, len(idx)):\n",
    "            ans = max(ans, (idx[i]-idx[i-1])//2)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: list[int]) -> int:\n",
    "        pos = []\n",
    "        for i, n in enumerate(seats):\n",
    "            if n==1:\n",
    "                pos.append(i)\n",
    "\n",
    "        dmax = 0\n",
    "        if seats[0] == 0:\n",
    "            dmax = max(dmax, pos[0])\n",
    "        if seats[-1] == 0:\n",
    "            dmax = max(dmax, len(seats) - 1 - pos[-1])\n",
    "        for i in range(len(pos)-1):\n",
    "            dmax = max(dmax, (pos[i+1] - pos[i])//2)\n",
    "\n",
    "        return dmax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        n = len(seats)\n",
    "        tmp = list()\n",
    "        m = 0\n",
    "        for i in range(n):\n",
    "            if seats[i] == 1:\n",
    "                tmp.append(i)\n",
    "                if len(tmp) == 1:\n",
    "                    m = i*2\n",
    "                else:\n",
    "                    m = max(m, tmp[-1] - tmp[len(tmp) - 2])\n",
    "            if i == n - 1 and seats[i] == 0:\n",
    "                m = max(m, 2*(i - tmp[-1]))\n",
    "            # print(tmp,m)\n",
    "        return m//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        n = len(seats)\n",
    "        s = []\n",
    "        for i in range(n):\n",
    "            if seats[i] != 0:\n",
    "                s.append(i)\n",
    "        res = 0\n",
    "        for i in range(len(s)-1):\n",
    "            res = max(res, (s[i+1]-s[i])//2)\n",
    "        res = max(res, s[0])\n",
    "        res = max(res, n-1-s[-1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        n = len(seats)\n",
    "        l, r = [-1] * n, [-1] * n\n",
    "        ans = [-1] * n\n",
    "        tmp = -1\n",
    "        for i in range(n):\n",
    "            if seats[i] == 1:\n",
    "                tmp = i\n",
    "                l[i] = -1\n",
    "                continue\n",
    "            l[i] = i - tmp if tmp != -1 else -1\n",
    "        # print(l)\n",
    "        tmp = -1\n",
    "        for i in reversed(range(n)):\n",
    "            if seats[i] == 1:\n",
    "                tmp = i\n",
    "                r[i] = -1\n",
    "                continue\n",
    "            r[i] = tmp - i if tmp != -1 else -1\n",
    "        # print(r)\n",
    "\n",
    "        for i in range(n):\n",
    "            if l[i] == -1:\n",
    "                ans[i] = r[i]\n",
    "                continue\n",
    "            if r[i] == -1:\n",
    "                ans[i] = l[i]\n",
    "                continue\n",
    "            ans[i] = min(l[i], r[i])\n",
    "        # print(ans)\n",
    "        return max(ans)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        \n",
    "        left = [len(seats)]*len(seats)\n",
    "        left_nearest = len(seats)\n",
    "        for i in range(len(seats)):\n",
    "            if seats[i]!=0:\n",
    "                left_nearest = i\n",
    "            else:\n",
    "                left[i]=left_nearest\n",
    "        \n",
    "        # print(left)\n",
    "\n",
    "        right = [len(seats)]*len(seats)\n",
    "        right_nearest=-1\n",
    "        for i in range(len(seats)-1,-1,-1):\n",
    "            if seats[i]!=0:\n",
    "                right_nearest = i\n",
    "            else:\n",
    "                right[i]=right_nearest\n",
    "        \n",
    "        # print(right)\n",
    "\n",
    "        ans = -1\n",
    "        for i in range(len(seats)):\n",
    "            if seats[i]==0:\n",
    "                ans = max(ans, min(abs(i-left[i]), abs(right[i]-i)))\n",
    "        \n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        n = len(seats)\n",
    "        minDis = [inf for _ in range(n)]\n",
    "        lastLeftSeat = inf\n",
    "        for i in range(n):\n",
    "            if seats[i] == 1:\n",
    "                lastLeftSeat = i\n",
    "            else:\n",
    "                if lastLeftSeat != inf:\n",
    "                    minDis[i] = i-lastLeftSeat\n",
    "        lastRightSeat = inf\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if seats[i] == 1:\n",
    "                minDis[i] = -inf \n",
    "                lastRightSeat = i\n",
    "            else:\n",
    "                if lastRightSeat != inf:\n",
    "                    minDis[i] = min(minDis[i], lastRightSeat-i)\n",
    "        # print(minDis)\n",
    "        return max(minDis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        n = len(seats)\n",
    "        a = []\n",
    "        for i in range(n):\n",
    "            if seats[i] == 1:\n",
    "                a.append(i)\n",
    "        m = len(a)\n",
    "        if m == 1:\n",
    "            return max(a[0],n-1-a[0])\n",
    "        ans = 0\n",
    "        for j in range(m-1):\n",
    "            ans = max(ans,(a[j+1]-a[j])//2)\n",
    "        return max(ans,a[0],n-1-a[-1])\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        n = len(seats)\n",
    "        p = [i for i, x in enumerate(seats) if x]\n",
    "        ans = 0\n",
    "        if p[0] > 0:\n",
    "            ans = max(ans, p[0])\n",
    "        if p[-1] < n-1:\n",
    "            ans = max(ans, n-1-p[-1])\n",
    "        for i in range(1, len(p)):\n",
    "            ans = max(ans, (p[i]-p[i-1])//2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        ans=[]\n",
    "        for i,j in enumerate(seats):\n",
    "            if j==1:\n",
    "                ans.append(i)\n",
    "        max1=max(len(seats)-ans[-1]-1,ans[0])\n",
    "        for i in range(1,len(ans)):\n",
    "            max1=max(max1,(ans[i]-ans[i-1])//2)\n",
    "        return max1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        n = len(seats)\n",
    "        left, leftGap = [], float(\"inf\")\n",
    "        for x in seats:\n",
    "            if x == 1:\n",
    "                leftGap = 0\n",
    "            else:\n",
    "                leftGap += 1\n",
    "            left.append(leftGap)\n",
    "        right, rightGap = deque(), float(\"inf\")\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if seats[i] == 1:\n",
    "                rightGap = 0\n",
    "            else:\n",
    "                rightGap += 1\n",
    "            right.appendleft(rightGap)\n",
    "        print(f\"left:{left}\")\n",
    "        print(f\"right:{right}\")\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if left[i] + right[i] == 0:\n",
    "                continue\n",
    "            ans = max(ans, min(left[i], right[i]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        people = []\n",
    "        for index, seat in enumerate(seats):\n",
    "            if seat == 1:\n",
    "                people.append(index)\n",
    "        dis = []\n",
    "        for i in range(len(people) - 1):\n",
    "            dis.append(people[i + 1] - people[i])\n",
    "        dis.append(people[0] * 2)\n",
    "        dis.append((len(seats) - people[-1] - 1) * 2)\n",
    "        return max(dis) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        k = [0]\n",
    "        for i in range(len(seats)):\n",
    "            if seats[i] == 1:\n",
    "                k.append(i)\n",
    "        k.append(len(seats)-1)\n",
    "        \n",
    "        print(k)\n",
    "        m = 0\n",
    "        for i in range(1,len(k)):\n",
    "            m = max(k[i]-k[i-1],m) if seats[k[i]] == 1 and seats[k[i-1]] == 1 else max((k[i]-k[i-1])*2,m)\n",
    "        return  max(m//2,1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        idx = []\n",
    "        bd = 0\n",
    "        bound = [0]\n",
    "        for i in range(len(seats)):\n",
    "            if seats[i] == 1:\n",
    "                bound.append(i)\n",
    "        bound.append(len(seats)-1)\n",
    "        for i in range(0, len(bound)-1):\n",
    "            if bound[i+1] - bound[i] > bd:\n",
    "                bd = bound[i+1] - bound[i]\n",
    "        res1 = bound[1]-0\n",
    "        res2 = bound[-1] - bound[-2]\n",
    "        res3 = bd // 2\n",
    "        res = max([res1, res2, res3])\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        left = [-1] * len(seats)\n",
    "        right = [-1] * len(seats)\n",
    "\n",
    "        last = -2*len(seats)\n",
    "        for i, ocupied in enumerate(seats):\n",
    "            if ocupied == 1:\n",
    "                last = i\n",
    "            else:\n",
    "                left[i] = last\n",
    "        \n",
    "        last = 2*len(seats)\n",
    "        for i in range(len(seats)-1, -1, -1):\n",
    "            if seats[i] == 1:\n",
    "                last = i\n",
    "            else:\n",
    "                right[i] = last\n",
    "        \n",
    "        res = 1\n",
    "\n",
    "        for i, ocupied in enumerate(seats):\n",
    "            if ocupied == 1:\n",
    "                continue\n",
    "            res = max(res, min(i - left[i], right[i] - i))\n",
    "\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        index = 0\n",
    "        seated = []\n",
    "        for i in range(len(seats)):\n",
    "            if seats[i] == 1:\n",
    "                seated.append(i)\n",
    "        max_diff = 0\n",
    "        i = 1\n",
    "        while i < len(seated):\n",
    "            max_diff = max(max_diff, (seated[i] - seated[i-1]) // 2)\n",
    "            i += 1\n",
    "        max_diff = max(max_diff, seated[0])\n",
    "        max_diff = max(max_diff, len(seats) - seated[-1] - 1)\n",
    "        return max_diff\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        res=[]\n",
    "        n=len(seats)\n",
    "        for i in range(n):\n",
    "            if seats[i]==1:\n",
    "                res.append(i)\n",
    "        n=len(res)\n",
    "        ans=1\n",
    "        #枚举两两中间\n",
    "        for i in range(1,n):\n",
    "            pre,suf=res[i],res[i-1]\n",
    "            ans=max(ans,(pre-suf)>>1)\n",
    "        ans=max(ans,res[0])\n",
    "        ans=max(ans,len(seats)-1-res[-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        res=[]\n",
    "        n=len(seats)\n",
    "        for i in range(n):\n",
    "            if seats[i]==1:\n",
    "                res.append(i)\n",
    "        n=len(res)\n",
    "        ans=1\n",
    "        #枚举两两中间\n",
    "        for i in range(1,n):\n",
    "            pre,suf=res[i],res[i-1]\n",
    "            ans=max(ans,(pre-suf)>>1)\n",
    "        ans=max(ans,res[0])\n",
    "        ans=max(ans,len(seats)-1-res[-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        if len(seats) == 2:\n",
    "            return 1\n",
    "        r = []\n",
    "        for j in range(0, len(seats)):            \n",
    "            if seats[j]==1:\n",
    "                r.append(j)\n",
    "        a = r[0]\n",
    "        b = r[-1]\n",
    "        if a == b:\n",
    "            if a-0 > len(seats)-a-1:\n",
    "                return a\n",
    "            else:\n",
    "                return len(seats)-a-1\n",
    "        \n",
    "        c = []\n",
    "        c.append(a)\n",
    "        c.append(len(seats)-b-1)\n",
    "\n",
    "        for k in range(0, len(r)-1):\n",
    "            c.append((r[k+1]-r[k])//2)\n",
    "        d = 0\n",
    "        for q in range(0, len(c)):\n",
    "            if c[q]>d:\n",
    "                d = c[q]\n",
    "        return d\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        dp1 = [-1] * len(seats)\n",
    "        dp2 = [-1] * len(seats)\n",
    "        maxSeat = -1\n",
    "        for i in range(len(seats)):\n",
    "            if seats[i] == 1:\n",
    "                maxSeat = i\n",
    "            if seats[i] == 0:\n",
    "                dp1[i] = maxSeat\n",
    "        minSeat = -1\n",
    "        for j in range(len(seats)-1, -1, -1):\n",
    "            if seats[j] == 1:\n",
    "                minSeat = j\n",
    "            if seats[j] == 0:\n",
    "                dp2[j] = minSeat\n",
    "        maxNum = 0\n",
    "        for i in range(len(seats)):\n",
    "            if dp1[i] > -1 and dp2[i] > -1:\n",
    "                maxNum = max(maxNum, min(abs(i-dp1[i]), abs(i-dp2[i])))\n",
    "            elif dp1[i] == -1 and dp2[i] == -1:\n",
    "                continue\n",
    "            else:\n",
    "                maxNum = max(maxNum, abs(i-dp1[i]) if dp1[i] > -1 else abs(i-dp2[i]))\n",
    "\n",
    "        return maxNum\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        idx=[]\n",
    "        for i in range(len(seats)):\n",
    "            if seats[i]==1:\n",
    "                idx.append(i)\n",
    "        distance = [(idx[i] - idx[i-1])//2 for i in range(1,len(idx))]\n",
    "        distance.append(idx[0])\n",
    "        distance.append(len(seats)-1-idx[-1])\n",
    "        return max(distance)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        occu = [i for i in range(len(seats)) if seats[i] == 1]\n",
    "        pre = None\n",
    "        d = 0\n",
    "        for i in occu:\n",
    "            if pre is not None:\n",
    "                d = max(d, (i-pre)//2)\n",
    "            pre = i\n",
    "\n",
    "        return max(d, occu[0], len(seats)-occu[-1]-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        cur=[]\n",
    "        temp=0\n",
    "        loca=0\n",
    "        for k,v in enumerate(seats):\n",
    "            if v ==1:\n",
    "                cur.append(k)\n",
    "                temp = max(temp, k-loca)\n",
    "                loca=k\n",
    "        if len(cur)==1:\n",
    "            return max(cur[0], len(seats)-cur[0]-1)\n",
    "        temp = temp//2\n",
    "        temp = max(temp, len(seats)-cur[-1]-1)\n",
    "        temp = max(cur[0], temp)\n",
    "        return temp\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        st = [i for i in range(len(seats)) if seats[i]==1]\n",
    "        return max([st[0], len(seats)-st[-1]-1]+[(st[i+1]-st[i])//2 for i in range(len(st)-1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        if len(seats) == 2:            \n",
    "            return 1\n",
    "        r = []\n",
    "        for j in range(0, len(seats)):            \n",
    "            if seats[j]==1:\n",
    "                r.append(j)\n",
    "        a = r[0]\n",
    "        b = r[-1]\n",
    "        if a == b:\n",
    "            if a-0 > len(seats)-a-1:\n",
    "                return a\n",
    "            else:\n",
    "                return len(seats)-a-1\n",
    "        \n",
    "        c = []\n",
    "        c.append(a)\n",
    "        c.append(len(seats)-b-1)\n",
    "\n",
    "        for k in range(0, len(r)-1):\n",
    "            c.append((r[k+1]-r[k])//2)\n",
    "        print(c)\n",
    "        d = 0\n",
    "        for q in range(0, len(c)):\n",
    "            if c[q]>d:\n",
    "                d = c[q]\n",
    "        # if d == 1:\n",
    "        #     e =1\n",
    "        # else:\n",
    "        #     e = d//2\n",
    "        return d\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        n = len(seats)\n",
    "        p = []\n",
    "        re = 0\n",
    "        d = {}\n",
    "        k = 0\n",
    "        t = 0\n",
    "        for i in range(n):\n",
    "            if seats[i] == 1:\n",
    "                p.append(i)\n",
    "        k = 0\n",
    "        m = len(p)\n",
    "        if m == 0:\n",
    "            return n-1\n",
    "        for i in range(n):\n",
    "            if seats[i] == 0:\n",
    "                if i<p[k]:\n",
    "                    l = p[k] - i\n",
    "                    if l > re:\n",
    "                        re = l\n",
    "                if k < m-1:\n",
    "                    while i > p[k + 1]:\n",
    "                        k = k + 1\n",
    "                        if k+1 >= m-1:\n",
    "                            break\n",
    "                if k+1>=m:\n",
    "                    l = n - 1 - p[-1]\n",
    "                    if l > re:\n",
    "                        re = l\n",
    "                    break\n",
    "                elif p[k]<i<p[k+1]:\n",
    "                    l = min(i-p[k],p[k+1]-i)\n",
    "                    if l > re:\n",
    "                        re = l\n",
    "        return re\n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        l = [-10000000]\n",
    "        \n",
    "        n = len(seats)\n",
    "        for i in range(n) :\n",
    "            if seats[i] == 1 :\n",
    "                l.append(i)\n",
    "        l.append(10000000000)\n",
    "        ans = [0]*n\n",
    "        ll = 0\n",
    "        rr = 1\n",
    "        for i in range(n) :\n",
    "            if l[rr]==i :\n",
    "                ll+=1\n",
    "                rr+=1\n",
    "\n",
    "            else :\n",
    "\n",
    "                ans[i] = min(i-l[ll],l[rr]-i)\n",
    "\n",
    "        return max(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        idx = []\n",
    "        if seats.count(1) == 1:\n",
    "            return max(seats.index(1), len(seats) - 1 - seats.index(1))\n",
    "        while 1 in seats:\n",
    "            temp = seats.index(1)\n",
    "            idx.append(temp)\n",
    "            seats[temp] = 0\n",
    "\n",
    "        l = [idx[i+1] - idx[i] for i in range(len(idx) - 1)]\n",
    "        return max(max(l) // 2, idx[0], len(seats) - 1 - idx[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        seatidx = []\n",
    "        emptyidx = []\n",
    "        for i, item in enumerate(seats):\n",
    "            if item == 1:\n",
    "                seatidx.append(i)\n",
    "            elif item == 0:\n",
    "                emptyidx.append(i)\n",
    "\n",
    "        dist1 = 0\n",
    "        if emptyidx[0] == 0:\n",
    "            dist1 = seatidx[0] - 0\n",
    "\n",
    "        dist2 = 0\n",
    "        if emptyidx[-1] == len(seats)-1:\n",
    "            dist2 = len(seats)-seatidx[-1]-1  \n",
    "\n",
    "        dist3 = 0\n",
    "        for i in range(len(seatidx)-1):\n",
    "            l = (seatidx[i+1] - seatidx[i]) \n",
    "            if l >= dist3:\n",
    "                dist3 = l\n",
    "\n",
    "        return max(dist1,dist2,dist3//2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        n =len(seats)\n",
    "        a = 0\n",
    "        list1 = []\n",
    "\n",
    "        for i in range(len(seats)):\n",
    "            if seats[i] == 1:\n",
    "                a +=1\n",
    "                list1.append(i)\n",
    "\n",
    "\n",
    "        m=len(list1)\n",
    "        if a == 1:\n",
    "            tem = seats.index(1)\n",
    "            if n-1 - tem > tem:\n",
    "                return n-1 -tem\n",
    "            else:\n",
    "                return tem\n",
    "        l = [0]*(m-1)\n",
    "        for i in range(m-1):\n",
    "            l[i] = list1[i+1]-list1[i]\n",
    "        num = max(max(l)//2,list1[0],(n-1-list1[-1]))\n",
    "        print(num)\n",
    "        print(max(l))\n",
    "        if num == max(l)//2:\n",
    "            a = l.index(max(l))\n",
    "            return min((list1[a]+list1[a+1])//2-list1[a],list1[a+1]-(list1[a]+list1[a+1])//2)\n",
    "        else:\n",
    "            return num\n",
    "        # now = [0]*n\n",
    "        # for i in range(i):\n",
    "        #     now[i] =sum([abs(i-k) for k in list1])\n",
    "        # print(now)\n",
    "        # end = now.index(min(now))\n",
    "        return end\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        res = []\n",
    "        # 统计有人位置的索引\n",
    "        ind = []\n",
    "        for i in range(len(seats)):\n",
    "            if seats[i] == 1:\n",
    "                ind.append(i)\n",
    "\n",
    "        # 先考虑首尾没人的情况\n",
    "        if ind[0] != 0:\n",
    "            res.append(ind[0])\n",
    "        if ind[-1] != len(seats)-1:\n",
    "            res.append(len(seats)-1-ind[-1])\n",
    "        \n",
    "        # 再考虑中间两个有人作为之间的情况\n",
    "        for i in range(len(ind)-1):\n",
    "            res.append((ind[i+1] - ind[i]) // 2)\n",
    "\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        a = [0] * (len(seats) + 1)\n",
    "        b = [0] * (len(seats) + 1)\n",
    "        n = len(seats)\n",
    "        # 获取左边的位置\n",
    "        pre = 1e9\n",
    "        for i in range(n):\n",
    "            if seats[i] == 1:\n",
    "                pre = i\n",
    "            else:\n",
    "                a[i] = pre\n",
    "        # 获取右边的位置\n",
    "        nex = 1e9\n",
    "        for i in range(n - 1,-1,-1):\n",
    "            if seats[i] == 1:\n",
    "                nex = i\n",
    "            else:\n",
    "                b[i] = nex\n",
    "        print(a)\n",
    "        print(b)\n",
    "        maxn = -1e9\n",
    "        for i in range(n):\n",
    "            if seats[i] != 1:\n",
    "                maxn = max(maxn,min(abs(i - a[i]),abs(i - b[i])))\n",
    "        return maxn\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        seated = []\n",
    "        for i,seat in enumerate(seats):\n",
    "            if seat == 1:\n",
    "                seated.append(i)\n",
    "        print(seated)\n",
    "        max_distance = max(seated[0], len(seats)-1-seated[-1])\n",
    "        n = len(seated)\n",
    "        for i in range(1, n):\n",
    "            max_distance = max(max_distance, (seated[i] - seated[i-1]) // 2)\n",
    "        return max_distance\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        n = len(seats) \n",
    "        gaps = []\n",
    "        for i, val in enumerate(seats):\n",
    "            if val: gaps.append(i)\n",
    "        diffs = []\n",
    "        for i in range(1,len(gaps)):\n",
    "            diffs.append(gaps[i] - gaps[i - 1])\n",
    "\n",
    "        ans = 0\n",
    "        if diffs:\n",
    "            ans = max(val//2 for val in diffs)\n",
    "        if seats[0] == 0:\n",
    "            ans = max(ans, gaps[0])\n",
    "        if seats[-1] == 0:\n",
    "            ans = max(ans, n - 1 - gaps[-1])\n",
    "        return ans \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        seats = seats[::-1] + seats + seats[::-1]\n",
    "        n = len(seats)\n",
    "        i , j = 0, 0\n",
    "        res = 0\n",
    "        while i < n:\n",
    "            if seats[i] == 0:\n",
    "                for j in range(i+1, n):\n",
    "                    if seats[j] == 0:\n",
    "                        continue\n",
    "                    else:\n",
    "                        break\n",
    "                res = max(res, j - i) \n",
    "            i += 1\n",
    "          \n",
    "        return (res+1) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        res = 1\n",
    "        num_seats = len(seats)\n",
    "        people = [k for k, v in zip(range(num_seats), seats) if v==1]\n",
    "        temp = []\n",
    "        for i in range(len(people)-1):\n",
    "            temp.append((people[i+1]-people[i])//2)\n",
    "  \n",
    "        if temp != []:\n",
    "            res = max(temp)\n",
    "\n",
    "        for i in range(len(seats)):\n",
    "            if seats[i] == 1:\n",
    "                continue\n",
    "            if i < people[0]:\n",
    "                res = max(res, people[0] - i)\n",
    "            if i > people[-1]:\n",
    "                res = max(res, num_seats-1-people[-1])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        n = len(seats)\n",
    "        minDis = [inf for _ in range(n)]\n",
    "        lastLeftSeat = inf\n",
    "        for i in range(n):\n",
    "            if seats[i] == 1:\n",
    "                lastLeftSeat = i\n",
    "            else:\n",
    "                if lastLeftSeat != inf:\n",
    "                    minDis[i] = i-lastLeftSeat\n",
    "        lastRightSeat = inf\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if seats[i] == 1:\n",
    "                minDis[i] = -inf \n",
    "                lastRightSeat = i\n",
    "            else:\n",
    "                if lastRightSeat != inf:\n",
    "                    minDis[i] = min(minDis[i], lastRightSeat-i)\n",
    "        print(minDis)\n",
    "        return max(minDis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        indexes = [idx for idx, occupied in enumerate(seats) if occupied]\n",
    "        print(indexes)\n",
    "        from itertools import pairwise\n",
    "        r = max(((b - a) // 2 for a, b in pairwise(indexes)), default=0)\n",
    "        r = max(r, indexes[0], len(seats) - 1 - indexes[-1])\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistToClosest(self, seats: List[int]) -> int:\n",
    "        st = []\n",
    "        n = len(seats)\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "        for i in range(n):\n",
    "            while (st and seats[st[-1]] < seats[i]):\n",
    "                right[st.pop()] = i\n",
    "            # if st:\n",
    "            #     left[i] =  st[-1]\n",
    "            st.append(i)\n",
    "        st = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while (st and seats[st[-1]] < seats[i]):\n",
    "                left[st.pop()] = i\n",
    "            # if st:\n",
    "            #     left[i] =  st[-1]\n",
    "            st.append(i)        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if seats[i] == 0:\n",
    "                if left[i] == -1:\n",
    "                    ans = max(ans, right[i]-i)\n",
    "                elif right[i] == n:\n",
    "                    ans = max(ans, i - left[i])\n",
    "                else:\n",
    "                    ans = max(ans, min(i -left[i], right[i]-i))\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
